Typically a problem can be defined by decision variables, an objective function and functional constraints. Decision variables are used to represent decisions that need to be made, while constraints describe the logical or physical conditions that the decision variables must obey. When configuring a system to solve or optimize a problem, these variables and constraints are input to the system. For example, considering the workforce management problem, a workforce manager may want to know which engineers to schedule to which task, and a corresponding decision variable may include a discrete variable with possible values comprising the different engineers, while the constraints may include the complexity of the tasks involved, skill level of technician, the duration of tasks and travel time etc.
Conventionally, a model of the problem is set up using a digital processor, and the model, or problem model, is subject to at least some of the aforementioned constraints. Different solutions to the problem can be obtained by changing decision variables of the model. For example, in the engineer-scheduling problem, the order in which engineers are scheduled to complete their tasks can be changed and other variables, such as the duration of the day during which they work, can be altered. The resulting schedules can be tested against certain objective values such as the amount of time that individual engineers are idle or are travelling, and a schedule may be chosen on the basis of whichever schedule solution best satisfies the objective values for the solution.
Thus, the problem model can be used to calculate a number of candidate solutions, which are then compared on the basis of their corresponding objective values to determine the best solution.
It would be possible to compute each possible solution for the range of values of all of the variables and then search amongst the resulting solutions for a solution which best meets the objective values. This is known as an exact searching method. Sophisticated exact searching methods normally use a tree representation for enumerating all candidate solutions. Relational constraints are used to prune parts of the tree that lead to infeasible solutions, thus reducing the searching effort.
Exact search techniques such as linear programming may be applied to the problem model. With linear programming methods are applied to complex problems, which have many and disparate types of input variables, a significant data processing overhead is involved. In more sophisticated systems, specialised mechanisms may be devised which, after a change has been made to some of the input variables, restrict the computations to only the affected parts of the problem model. These mechanisms need to be coded for each particular problem requiring expert knowledge from the programmer. Furthermore, they are tedious to implement and maintain for realistic problems, which are of complex nature.
As an alternative to exact search methods, a heuristic search can be carried out. In a heuristic search method, rather than compute or enumerate each possible candidate solution, an individual candidate solution is taken, and then one or more of the values of the decision variables used in the computation of the candidate solution is changed. A new solution is computed on the basis of the changed variables and a determination is made of whether the newly computed solution is better than the first. The process may be repeated a number of times until the resulting solution results in optimization of the objective values.
A number of different heuristic searching techniques are known in the art for optimizing the solution for the problem model. For example, in a so-called single solution or local search technique, a first solution is taken and then perturbed to determine whether a better solution can be obtained when processed by the problem model. In a so-called population search technique, a number of solutions are obtained and a so-called genetic algorithm may be used to combine parts of the solutions into new solutions to be tested with the problem model.
Hitherto, heuristic search methods have been used to optimize solutions to complex, real-world problems involving large numbers of variables. For example, proposals have been made to use heuristic search methods optimize schedules used in workforce management, where field service engineers may need to perform repair tasks at different locations at different time of the day, according to a schedule. The schedule needs to be optimized as a function of the travel required by the engineers to complete their allocated tasks, the number of tasks left unallocated given the available number of engineers, and delays in task execution, the engineer skills and how well they match to task requirements and other factors such as the urgency of the individual tasks. Heuristic search methods have also been proposed for optimizing the scheduling of telephone calls, e.g. incoming calls to operations in a call center, and also for the allocation of frequency bands for use by radio transmitters e.g. in a cellular mobile telecommunications network.
However, difficulties have been encountered in formulating suitable problem models for use with heuristic search optimization methods, and an individual problem model usually needs to be specially crafted and set up for a particular problem. Furthermore it has been found that different heuristic searching techniques have different levels of efficiencies for different problem models so that, when a particular problem model has been designed and a particular heuristic search technique associated with it, it is extremely difficult to change the configuration without extensive reprogramming.
The present invention seeks to overcome these difficulties.